#include <cstdio>
#include <iostream>
using namespace std;

char buf[(int) 5e7], *fs = buf;

inline int gn() { 
    int k = 0;
    char c = *fs++;
    for (; !isdigit(c); c = *fs++);
    for (; isdigit(c); c = *fs++) k = k * 10 + c - '0';
    return k;
}

const int maxn = 1e6 + 3;

int dis[maxn], n, maxc, v[maxn], c[maxn];

int main() { 
    freopen("bus.in", "r", stdin);
    freopen("bus.out", "w", stdout);
    fread(buf, 1, (int) 5e7, stdin);
    n = gn(), maxc = gn();
    for (int i = 0; i < n; i++) {
        c[i] = gn(), v[i] = gn();
        dis[i] = (int)1e9 + 3;
    }
    dis[n] = (int)1e9 + 3;
    dis[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + c[i], k = v[i]; j <= n; j += c[i], k += v[i]) {
            dis[j] = min(dis[j], dis[i] + k);
            if ((j !=n) and c[i] == c[j] and v[i] >= v[j]) 
                break;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dis[i] == (int)1e9 + 3) dis[i] = -1;
        printf("%d ", dis[i]);
    }
    putchar('\n');
}
